package com.wyr.leetcode.step1.number;

public class MissingNumber {
    /**
     * 268. 丢失的数字
     *
     * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
     */
    public int missingNumber(int[] nums) {
        // 数组的长度即代表是 0-n， 在这n+1个数后添加从0-n的每一个整数，共有2n+1个数
        // 在这2n+1个整数中，丢失的数字旨在后面n+1个整数中出现一次，其余数字都是出现2次
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans ^= nums[i];
        }
        for (int i = 0; i <= nums.length; i++) {
            ans ^= i;
        }
        return ans;
    }
}
